
var largestRectangleArea = function(heights) {
    if(heights.length === 0)return 0;
    if(heights.length === 1)return heights[0];

    heights.push(0);

    let area = 0,
        length = heights.length,
        cur = 0,
        stack = [];

    while(cur<length){
        //console.log("~~~",cur);
        if(stack.length === 0){
            stack.push({v:heights.shift(),i:++cur});
        }

        let tmp = heights.shift();
        cur++;

        //console.log("!!!",cur,"tmp",tmp,stack[stack.length-1].v);

        if(tmp>=stack[stack.length-1].v){
            stack.push({v:tmp,i:cur});
        }else{
            let s = stack.pop();
            //console.log(s,stack[stack.length-1]);
            while(stack.length>0 && s.v === stack[stack.length-1].v){
                s = stack.pop();
            }
            let tmpArea = s.v*(cur - s.i);

            //console.log("tmpArea",tmpArea,"tmp",0,"cur",cur,"s",s);

            if(area<tmpArea)area = tmpArea;

            if(stack.length===0){
                stack.push({v:tmp,i:s.i});
            }else if(tmp>=stack[stack.length-1].v){
                stack.push({v:tmp,i:s.i});
            }else{
                stack.push({v:stack[stack.length-1].v,i:s.i});
            }

            //if(tmp!=0)stack.push({v:tmp,i:s.i});
            heights.unshift(tmp);
            cur--;
            //console.log(cur,"heights",heights,"stack",stack);
        }
    }
    //console.log(cur);

    return area;
};

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if(matrix.length===0)return 0;
    let area = 0;

    let heights = [];
    matrix.forEach((str,index)=>{
        let length = str.length;
        let hs = [];
        for(let i=0;i<length;i++){
            if(str[i]!=="0"){
                if(index===0){
                    hs.push(1);
                }else{
                    hs.push(1+heights[index-1][i]);
                }
            }else{
                hs.push(0);
            }
        }
        heights.push(hs);
    });
    //return heights;
    heights.forEach(hs=>{
        let tmpArea = largestRectangleArea(hs);
        if(area<tmpArea)area=tmpArea;
    });
    return area;
};


console.log(maximalRectangle(
    [
        "10100",
        "10111",
        "11111",
        "10010"
    ]));